
public class MySingleList {
    //节点至少有两个域 节点内部类
    static class ListNode{
        public int val;
        public ListNode next;

        public ListNode(int val){
            this.val=val;
        }
    }
    public ListNode head;//不初始化，默认就是null
    public void createList(){
        ListNode listNode1=new ListNode(12);
        ListNode listNode2=new ListNode(23);
        ListNode listNode3=new ListNode(34);
        ListNode listNode4=new ListNode(45);
        ListNode listNode5=new ListNode(56);
        //new了五个节点
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;
        //节点间建立联系
        this.head=listNode1;

    }

    public static void main(String[] args) {
        MySingleList mySingleList=new MySingleList();
        //头插
        mySingleList.addFirst(15);
        mySingleList.addFirst(23);
        mySingleList.addFirst(34);
        mySingleList.addFirst(15);
        mySingleList.addFirst(56);
        //尾插
        mySingleList.addLast(58);
        mySingleList.addLast(35);
        //mySingleList.createList();
        mySingleList.display();
        System.out.println("长度"+mySingleList.size());
        System.out.println(mySingleList.contains(134));
        mySingleList.remove(1999);
        mySingleList.remove(56);
        mySingleList.display();
        mySingleList.removeAllKey(15);
        MySingleList.ListNode ret=mySingleList.reverseList();
        mySingleList.display(ret);
        mySingleList.display();

        MySingleList mySingleList1=new MySingleList();
        mySingleList1.addLast(12);
        mySingleList1.addLast(22);
        mySingleList1.addLast(32);
        mySingleList1.addLast(42);
        mySingleList1.addLast(52);
        mySingleList1.display();

        MySingleList mySingleList2=new MySingleList();
        mySingleList2.addLast(13);
        mySingleList2.addLast(23);
        mySingleList2.addLast(33);
        mySingleList2.addLast(43);
        mySingleList2.addLast(53);
        mySingleList2.display();


        MySingleList.ListNode newHead= mergeTwoLists(mySingleList1.head,mySingleList2.head);

        mySingleList1.display(newHead);
    }
    //打印列表中的数据  默认从头开始
    public void display(){
        ListNode cur=this.head;
        while(cur!=null){

            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println( );
    }
    //从指定节点newHead开始打印链表
    public void display(ListNode newHead){
        ListNode cur=newHead;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }


    //得到单链表的长度
    public int size(){
        //cur==null
        int count=0;
        ListNode cur=this.head;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    //头插法
    public void addFirst(int data){
        ListNode node=new ListNode(data);
        node.next=head;
        head=node;
    }
    //尾插法
    public void addLast(int data){
        ListNode node=new ListNode(data);
        ListNode cur=this.head;
        if(cur==null){
            this.head=node;
        }else{
            while(cur.next!=null){
                cur=cur.next;
            }
        }
        cur.next=node;
    }
    //任意位置插入，第一个数据节点为0号下标——>逻辑上的下标
    public void addIndex(int index,int data){
        if(index<0||index>size()){
            System.out.println("index位置不合法！");
            //报一个异常
            throw new IndexWrongFulException("index位置不合法！");
        }

        if(index==0){
            addFirst(data);
            return ;
        } else if (index==size()) {
            addLast(data);
            return;
        }else{
            //1.先走index-1步，找到cur
            ListNode cur=findIndexSubOne(index);
            ListNode node=new ListNode(data);
            //2.修改指向
            node.next=cur.next;
            cur.next=node;
        }
    }
    private ListNode findIndexSubOne(int index){
        ListNode cur=this.head;
        while(index-1!=0){
            cur=cur.next;
            index--;
        }
        return cur;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur=this.head;
        while(cur!=null){
            if(cur.val==key){

                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        if(this.head==null){
            return ;
        }
        //删除头节点
        if(this.head.val==key){
            this.head=this.head.next;
            return;
        }
        ListNode cur=findPrevOfKey(key);
        if(cur==null){
            System.out.println("没有你要删除的数字！");
            return;
        }
        ListNode del=cur.next;
        cur.next=del.next;

    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        if(this.head==null){
            return ;
        }
        ListNode prev= this.head;
        ListNode cur=this.head.next;
        while(cur!=null){
            if(cur.val==key){
                prev.next=cur.next;
                cur=cur.next;
            }else{
                prev=cur;
                cur=cur.next;
            }
            if(this.head.val==key){
                this.head=this.head.next;

            }
        }
    }
    private ListNode findPrevOfKey(int key){
        ListNode cur=this.head;
        while(cur.next!=null){
            if(cur.next.val==key){
                return cur;

            }
            cur=cur.next;
        }

        return null;
    }


    public void clear() {
        this.head=null;
    }
    public ListNode reverseList(){
        //没有节点
        if(this.head==null){
            return null;
        }
        //有一个节点
        if(this.head.next==null){
            return this.head;
        }
        ListNode cur=head.next;
        head.next=null;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=head;
            head=cur;
            cur=curNext;
        }
        return head;
    }
    public ListNode middleNode(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
    public ListNode findKthToTail( int k ) {
        // write code here
        if(k<=0||head==null){
            return null;
        }
        if(k<=0||k>size()){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(k-1!=0){
            fast=fast.next;
            if(fast==null){
                return null;
            }
            k--;
        }
        while(fast.next!=null){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }
    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode head1, MySingleList.ListNode head2) {
        MySingleList.ListNode NewHead=new MySingleList.ListNode(-1);
        ListNode tmp=NewHead;
        while(head1!=null&&head2!=null){
            if(head1.val< head2.val){
                tmp.next=head1;
                head1=head1.next;
            }else {
                tmp.next=head2;
                head2=head2.next;
            }
            tmp=tmp.next;
        }
        if(head1!=null){
            tmp.next=head1;
        }
        if(head2!=null){
            tmp.next=head2;
        }
        return NewHead.next;
    }
}

